package com.evan.review.basic.collection;

import android.os.Bundle;
import android.widget.TextView;
import androidx.appcompat.app.AppCompatActivity;
import com.evan.review.R;
import java.util.HashMap;
import java.util.Map;

/**
 * HashMap详解Activity
 * 
 * 本Activity详细讲解了HashMap的实现原理、特性和使用方法：
 * 1. HashMap的底层数据结构（数组+链表/红黑树）
 * 2. HashMap的添加、查找、删除操作原理
 * 3. HashMap的扩容机制与负载因子
 * 4. HashMap的哈希冲突处理
 * 5. JDK8对HashMap的优化（红黑树）
 * 6. 常见面试题与陷阱
 */
public class HashMapActivity extends AppCompatActivity {
    
    private TextView tvOutput;
    
    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_data_structure);
        
        setTitle("HashMap详解");
        
        tvOutput = findViewById(R.id.tv_output);
        
        // 展示HashMap基本原理
        demonstrateHashMapPrinciple();
        
        // 展示HashMap基本操作
        demonstrateHashMapOperations();
        
        // 展示HashMap扩容机制
        demonstrateHashMapResizing();
        
        // 展示HashMap与线程安全
        demonstrateHashMapThreadSafety();
        
        // 展示常见面试题
        demonstrateInterviewQuestions();
    }
    
    /**
     * 展示HashMap的基本原理
     */
    private void demonstrateHashMapPrinciple() {
        StringBuilder output = new StringBuilder();
        output.append("=== HashMap的底层原理 ===\n\n");
        
        // 1. 基本结构
        output.append("1. 基本数据结构：\n");
        output.append("• JDK 1.7：数组 + 链表\n");
        output.append("• JDK 1.8：数组 + 链表 + 红黑树\n\n");
        
        output.append("2. 内部组成：\n");
        output.append("• Node<K,V>[] table：哈希桶数组\n");
        output.append("• 默认初始容量：16（1 << 4）\n");
        output.append("• 默认负载因子：0.75f\n");
        output.append("• 扩容阈值：capacity * loadFactor\n\n");
        
        output.append("3. 重要特性：\n");
        output.append("• 允许null键和null值\n");
        output.append("• 非线程安全\n");
        output.append("• 不保证有序性\n");
        output.append("• 不保证顺序随时间保持不变\n\n");
        
        output.append("4. 红黑树优化（JDK 1.8+）：\n");
        output.append("• 当链表长度超过TREEIFY_THRESHOLD（默认8）时，链表转换为红黑树\n");
        output.append("• 当红黑树节点数小于UNTREEIFY_THRESHOLD（默认6）时，红黑树转回链表\n");
        output.append("• 红黑树转换的前提：桶数组长度至少为MIN_TREEIFY_CAPACITY（默认64）\n");
        
        updateOutput(output.toString());
    }
    
    /**
     * 展示HashMap的基本操作
     */
    private void demonstrateHashMapOperations() {
        StringBuilder output = new StringBuilder();
        output.append("\n=== HashMap的基本操作 ===\n\n");
        
        // 创建HashMap并填充数据
        Map<String, Integer> map = new HashMap<>();
        map.put("Java", 95);
        map.put("C++", 90);
        map.put("Python", 85);
        
        // 1. 添加元素
        output.append("1. 添加元素：\n");
        output.append("map.put(\"Java\", 95);\n");
        output.append("map.put(\"C++\", 90);\n");
        output.append("map.put(\"Python\", 85);\n\n");
        
        output.append("Put操作原理：\n");
        output.append("① 计算key的hash值\n");
        output.append("② 确定数组索引位置：(n - 1) & hash\n");
        output.append("③ 如果桶为空，直接插入\n");
        output.append("④ 如果桶中已有元素：\n");
        output.append("  - 若key相同，则更新value\n");
        output.append("  - 若key不同，JDK1.7采用头插法，JDK1.8采用尾插法添加到链表/红黑树\n");
        output.append("⑤ 检查是否需要扩容或链表转红黑树\n\n");
        
        // 2. 获取元素
        output.append("2. 获取元素：\n");
        output.append("map.get(\"Java\") = " + map.get("Java") + "\n");
        output.append("map.getOrDefault(\"Kotlin\", 0) = " + map.getOrDefault("Kotlin", 0) + "\n\n");
        
        output.append("Get操作原理：\n");
        output.append("① 计算key的hash值\n");
        output.append("② 确定桶位置：(n - 1) & hash\n");
        output.append("③ 如果是首节点，直接比较\n");
        output.append("④ 如果是链表，遍历链表比较\n");
        output.append("⑤ 如果是红黑树，按红黑树查找\n\n");
        
        // 3. 删除元素
        output.append("3. 删除元素：\n");
        output.append("map.remove(\"Python\") = " + map.remove("Python") + "\n");
        output.append("当前map：" + map + "\n\n");
        
        // 4. 遍历HashMap
        output.append("4. 遍历HashMap：\n");
        output.append("// 方式1：遍历EntrySet\n");
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            output.append("Key = " + entry.getKey() + ", Value = " + entry.getValue() + "\n");
        }
        
        output.append("\n// 方式2：遍历KeySet\n");
        for (String key : map.keySet()) {
            output.append("Key = " + key + ", Value = " + map.get(key) + "\n");
        }
        
        output.append("\n// 方式3：Java 8 Lambda表达式\n");
        output.append("map.forEach((k, v) -> System.out.println(\"Key = \" + k + \", Value = \" + v));\n");
        
        updateOutput(output.toString());
    }
    
    /**
     * 展示HashMap的扩容机制
     */
    private void demonstrateHashMapResizing() {
        StringBuilder output = new StringBuilder();
        output.append("\n=== HashMap的扩容机制 ===\n\n");
        
        // 1. 扩容触发条件
        output.append("1. 扩容触发条件：\n");
        output.append("• 当HashMap中的元素个数超过threshold值（capacity * loadFactor）时\n");
        output.append("• 例：默认容量16，负载因子0.75，当元素个数超过16*0.75=12时触发扩容\n\n");
        
        // 2. 扩容过程
        output.append("2. 扩容过程：\n");
        output.append("• 创建一个新的数组，容量为原数组的2倍\n");
        output.append("• JDK 1.7：rehash所有元素（重新计算哈希值）\n");
        output.append("• JDK 1.8优化：利用hash & oldCap判断元素新位置\n");
        output.append("  - 若为0：索引位置不变\n");
        output.append("  - 若为非0：新索引 = 原索引 + 原容量\n\n");
        
        // 3. 扩容成本
        output.append("3. 扩容成本：\n");
        output.append("• 时间复杂度：O(n)\n");
        output.append("• 涉及大量对象复制和哈希计算\n");
        output.append("• 频繁扩容会影响性能\n\n");
        
        // 4. 优化建议
        output.append("4. 优化建议：\n");
        output.append("• 如果预知数据量，初始化时指定合适容量：new HashMap<>(initialCapacity)\n");
        output.append("• initialCapacity = 预估元素数量 / 负载因子\n");
        output.append("• 尽量使键的hashCode均匀分布\n");
        
        updateOutput(output.toString());
    }
    
    /**
     * 展示HashMap的线程安全问题
     */
    private void demonstrateHashMapThreadSafety() {
        StringBuilder output = new StringBuilder();
        output.append("\n=== HashMap的线程安全问题 ===\n\n");
        
        // 1. 线程安全问题
        output.append("1. HashMap线程不安全表现：\n");
        output.append("• 在并发环境下可能导致死循环（JDK1.7）\n");
        output.append("• 可能导致数据丢失\n");
        output.append("• 可能读到脏数据\n\n");
        
        // 2. 线程安全的替代方案
        output.append("2. 线程安全的替代方案：\n");
        output.append("• HashTable：使用synchronized同步方法，性能较差\n");
        output.append("• Collections.synchronizedMap：使用synchronized代码块\n");
        output.append("• ConcurrentHashMap：分段锁（JDK1.7）或CAS+synchronized（JDK1.8）\n\n");
        
        // 3. ConcurrentHashMap简介
        output.append("3. ConcurrentHashMap特点：\n");
        output.append("• JDK 1.7：Segment分段锁（继承ReentrantLock）\n");
        output.append("• JDK 1.8：取消分段锁，采用CAS+synchronized实现\n");
        output.append("• 允许并发读取，写入操作线程安全\n");
        output.append("• 不允许null键和null值（HashMap允许）\n");
        
        updateOutput(output.toString());
    }
    
    /**
     * 展示HashMap相关面试题
     */
    private void demonstrateInterviewQuestions() {
        StringBuilder output = new StringBuilder();
        output.append("\n=== HashMap常见面试题 ===\n\n");
        
        // 1. 哈希冲突解决方案
        output.append("1. HashMap如何解决哈希冲突？\n");
        output.append("答：HashMap使用链地址法（链表/红黑树）解决哈希冲突。\n");
        output.append("当不同的key经过哈希计算后定位到同一个桶时：\n");
        output.append("• JDK 1.7：将新元素插入链表头部\n");
        output.append("• JDK 1.8：将新元素插入链表尾部\n");
        output.append("• 当链表长度超过8且数组长度超过64，转换为红黑树提高查询效率\n\n");
        
        // 2. HashMap和HashTable区别
        output.append("2. HashMap与HashTable的区别？\n");
        output.append("答：主要区别有：\n");
        output.append("• 线程安全：HashMap非线程安全；HashTable线程安全（同步方法）\n");
        output.append("• null值：HashMap允许null键和值；HashTable不允许null键和值\n");
        output.append("• 性能：HashMap性能较好；HashTable由于同步方法性能较差\n");
        output.append("• 继承关系：HashMap继承自AbstractMap；HashTable继承自Dictionary\n");
        output.append("• 迭代器：HashMap使用Iterator；HashTable使用Iterator和Enumeration\n");
        output.append("• 默认容量：HashMap默认16；HashTable默认11\n\n");
        
        // 3. HashMap和ConcurrentHashMap的区别
        output.append("3. HashMap与ConcurrentHashMap的区别？\n");
        output.append("答：主要区别：\n");
        output.append("• 线程安全：HashMap非线程安全；ConcurrentHashMap线程安全\n");
        output.append("• 实现方式：ConcurrentHashMap在JDK1.7使用分段锁，JDK1.8使用CAS+synchronized\n");
        output.append("• null值：HashMap允许null键和值；ConcurrentHashMap不允许null键和值\n");
        output.append("• 性能：ConcurrentHashMap在高并发环境下性能远优于HashMap\n\n");
        
        // 4. HashMap的哈希函数
        output.append("4. HashMap的哈希函数如何设计的？为什么要这样设计？\n");
        output.append("答：HashMap的hash方法（以JDK1.8为例）：\n");
        output.append("static final int hash(Object key) {\n");
        output.append("    int h;\n");
        output.append("    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);\n");
        output.append("}\n\n");
        
        output.append("设计原理：\n");
        output.append("• 高16位与低16位异或：充分利用高位和低位特征，减少哈希冲突\n");
        output.append("• 确定桶位置：(n - 1) & hash，其中n是数组长度\n");
        output.append("• 由于n通常较小，如16，与操作主要取决于hash的低位\n");
        output.append("• 异或操作使高位也能影响最终结果，更均匀分布\n\n");
        
        // 5. HashMap的容量为什么是2的幂
        output.append("5. 为什么HashMap的容量必须是2的幂？\n");
        output.append("答：主要原因：\n");
        output.append("• 计算索引位置采用：(n - 1) & hash，当n为2的幂时，n-1的二进制全为1\n");
        output.append("• 这样与hash进行与操作能够充分利用hash值的特征，减少冲突\n");
        output.append("• 若n不是2的幂，某些bit位上为0，会增加冲突概率\n");
        output.append("• 另外，2的幂便于优化：求模运算(%)转为位运算(&)，提高性能\n");
        
        updateOutput(output.toString());
    }
    
    /**
     * 更新输出文本
     */
    private void updateOutput(String text) {
        tvOutput.append(text);
    }
} 